// m

// 给定两个整数数组nums1和nums2
// 要求计算两个数组中公共的，长度最长的子数组长度
// 解题思路：动态规划
// 1. 定义状态： dp[i][j]表示为：以下标i-1结尾的nums1和以下标j-1结尾的nums2的最长重复子数组长度
// 2. 两重遍历nums1、nums2，计算dp[i][j]
//      1. 如果nums1[i] === nums2[j],则当前元素可以构成公共子数组，则dp[i][j] = dp[i-1][j-1] + 1
//      2. 如果nums1[i] !== nums2[j],则当前元素不能构成公共子数组，则dp[i][j] = 0
// 3. 最后用res记录下最大的dp[i][j]即为答案

function findLength(nums1, nums2) {
    let size1 = nums1.length
    let size2 = nums2.length
    let dp = new Array(size1 + 1).fill(0).map(() => new Array(size2 + 1).fill(0))
    let res = 0
    for (let i = 1; i <= size1; i++) {
        for (let j = 1; j <= size2; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            if (dp[i][j] > res) {
                res = dp[i][j]
            }
        }
    }
    return res
}
let nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7]
console.log(findLength(nums1, nums2));